package com.test.daily.leetcode.y2022.m07.day0723.v04;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/23 下午 08:25
 * @version: 1.0
 */
public class Solution {
    public static class UnionFind2 {
        public int[] parent;
        public int[] help;
        public int[] size;
        public int sets;
        public int col;
        public int[][] board;

        public UnionFind2(int[][] board) {
            this.board = board;
            int m = board.length;
            int n = board[0].length;
            this.col = board[0].length;
            int len = index(m, n);
            parent = new int[len];
            help = new int[len];
            size = new int[len];
            sets = len;
            for (int i = 0; i < len; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        public void connect(int rowi, int coli, int rowj, int colj){
            if(this.board[rowi][coli] == 1 && this.board[rowj][colj] == 1){
                union(rowi, coli, rowj, colj);
            }
            connect(rowi, coli,rowj, colj);
            connect(rowi, coli,rowj, colj);
            connect(rowi, coli,rowj, colj);
            connect(rowi, coli,rowj, colj);
        }
        public void union(int rowi, int coli, int rowj, int colj){
            int indexi = index(rowi, coli);
            int indexj = index(rowj,colj);
            int fatheri = findFather(indexi);
            int fatherj = findFather(indexj);
            if(fatheri != fatherj){
                int sizei = size[fatheri];
                int sizej = size[fatherj];
                if(sizei > sizej){
                    size[fatherj] = sizei + sizej;
                    parent[fatheri] = fatherj;
                } else {
                    size[fatheri] = sizei + sizej;
                    parent[fatherj] = fatheri;
                }
                sets--;
            }

        }
        public int size(){
            return sets;
        }
        public int findFather(int i){
            int hi = 0;
            while(i != parent[i]){
                help[hi++] = i;
            }
            for (hi--; hi >= 0; hi--) {
                parent[help[hi]] = i;
            }
            return i;
        }
        public boolean isSame(int i, int j){
            return findFather(i) == findFather(j);
        }

        public int index(int rowi, int coli) {
            return rowi * this.col + coli;
        }
    }
}
